Matrix Decomposition Method, Full Data

Vo and Park (2016) used a matrix decomposition approach to estimate background, foreground and noise in EM images. The math behind their method was worked out by Zhang et al. (2013) That is, if \(Y\) is a \(m\times n\) matrix where \(y_{ij}\) is the intensity value at the \(x\) and \(y\) locations. Then \(Y\) can be decomposed into \(B\), \(F\) and \(E\) corresponding to background, foreground and error, respectively, through \[Y = B + F + E.\]

\(B\) is estimated first using a regularized low-rank approximation \[\hat B_\lambda=\sum_{k=1}^p\hat{\mathbf{u}}_\lambda\hat{\mathbf{v}}_\lambda^\top\] where \(\hat{\mathbf{u}}_\lambda\) is the \(m\times 1\) unnormalized left singular vector estimated using regularized, robust SVD with penalty parameter \(\lambda\) and \(\hat{\mathbf{v}}_\lambda\) is the \(n\times 1\) right singular vector with unit norm estimated using RRSVD with penalty \(\lambda\). The rank of the approximation and the penalty parameter \(\lambda\) needs to be chosen on a case by case basis. A few example estimates of \(B\) with different \(\lambda\) values is below. Each of the estimates is an \(8^{th}\) degree approximation. Similar to regularized regression, large values of \(\lambda\) smooth out the background estimate while small values result in a very s.

#Create 'Bhat_list' object, takes a while so only run once and load the result in the next chunck
#Robust SVD of ex_frame in order to estimate background matrix (section 2.1), rank p
p <- 1
lams <- c(0,1,10,20,50)
Bhat_list <- vector("list",length(lams))
s_s <- matrix(0,length(lams),p)
for(j in 1:length(lams)){
  Bhat <- matrix(0,256,256)
  y <- ex_frame
  for(i in 1:p){
    y <- ex_frame - Bhat
    rsvdi <-  RobRSVD(y, irobust=TRUE, niter=100,uspar = lams[j], vspar = lams[j])
    Bhat <- Bhat + rsvdi$u%*%t(rsvdi$v)*rsvdi$s
    s_s[j,i] <- rsvdi$s
  }
  Bhat_list[[j]] <- Bhat
}
#plot(s_s[2,-c(1:2)])
#save(Bhat_list,file="/Users/stan070/Documents/AIM Project (Lisa)/streaming-tcs/EM_Use_Case/Write_Ups/Bhat.Rdata")
load("~/Documents/AIM Project (Lisa)/streaming-tcs/EM_Use_Case/Write_Ups/Bhat.Rdata")
Vo_method_df <- data.frame(x=m1_dat$x,y=m1_dat$y, Y = matrix(t(ex_frame),ncol=1))
Vo_method_df$Bhat <- matrix(t(Bhat_list[[1]]),ncol=1)
plot1 <- qplot(x,y,colour=Bhat,data=Vo_method_df)+theme_em()+ggtitle(expression(lambda==0))
Vo_method_df$Bhat <- matrix(t(Bhat_list[[2]]),ncol=1)
plot2 <- qplot(x,y,colour=Bhat,data=Vo_method_df)+theme_em()+ggtitle(expression(lambda==1))
Vo_method_df$Bhat <- matrix(t(Bhat_list[[3]]),ncol=1)
plot3 <- qplot(x,y,colour=Bhat,data=Vo_method_df)+theme_em()+ggtitle(expression(lambda==10))
Vo_method_df$Bhat <- matrix(t(Bhat_list[[4]]),ncol=1)
plot4 <- qplot(x,y,colour=Bhat,data=Vo_method_df)+theme_em()+ggtitle(expression(lambda==20))
Vo_method_df$Bhat <- matrix(t(Bhat_list[[5]]),ncol=1)
plot5 <- qplot(x,y,colour=Bhat,data=Vo_method_df)+theme_em()+ggtitle(expression(lambda==50))
grid.arrange(plot1,plot2,plot3,plot4,plot5,nrow=1)

Vo_method_df$Bhat <- matrix(t(Bhat_list[[2]]),ncol=1)
rm(Bhat_list)

The decomposition of the original data (\(Y\), left plot) into background (\(B\), middle plot) and leftover (\(F+E\), right plot) using \(\lambda=1\) is below. The right plot does seem to have the left-to-right gradient removed, but it lightens the node up a bit too much.

Vo_method_df$Ohat <- Vo_method_df$Y - Vo_method_df$Bhat
truth <- qplot(x,y,colour=Y,data=Vo_method_df)+theme_em()+ggtitle("Y (original)")
bground <- qplot(x,y,colour=Bhat,data=Vo_method_df)+theme_em()+ggtitle("B (background)")
leftover <- qplot(x,y,colour=Ohat,data=Vo_method_df)+theme_em()+ggtitle("F+E (leftover)")
grid.arrange(truth,bground,leftover,nrow=1)

p <- 16
lambda <- 1
imgs <- vector("list",p)
all_plots <- vector("list",p)
approx <- matrix(0,256,256)
s_s <- rep(NA,p)
for(i in 1:p){
  y <- ex_frame - approx
  rsvdi <-  RobRSVD(y, irobust=TRUE, niter=500,uspar = lambda, vspar = lambda)
  imgs[[i]] <-  rsvdi$u%*%t(rsvdi$v)*rsvdi$s
  approx <- approx + imgs[[i]]
  s_s[i] <- rsvdi$s
  one_d_df <- data.frame(x=m1_dat$x,y=m1_dat$y, Int=matrix(t(imgs[[i]]),ncol=1))
  all_plots[[i]] <- qplot(x,y,colour=Int,data=one_d_df)+theme_em()+ggtitle(paste("Dimension",i))
}
#plot(s_s)
grid.arrange(grobs=all_plots,nrow=4,ncol=4)

#sum(s_s)/(256^2)

They then use the robust, regularized SVD approach again to decompose what’s left over (\(O\)) into foreground and residual, but I haven’t gotten that to give consistent results. Instead, I apply Maggie’s EM approach with no background to cluster the “left-over” pixels into growth and non-growth.

#Apply EM without background adjustment
mean_res <- EM_alg_mu_cpp(z=Vo_method_df$Ohat,p = rep(1/5,5), mu = c(-50,0,25,50,100), sigma = rep(4,5),eps = 1e-5,maxit = 1000)
Vo_method_df$Mean_class <- as.factor(apply(mean_res$wmat,1,which.max))
g_nong <- qplot(x,y,colour=Mean_class,data=Vo_method_df,size=I(.1))+theme_em()+scale_colour_manual(values=c(1,1,2,2,2))+ggtitle("Growth")
grid.arrange(truth,g_nong,nrow=1)

#hist(Vo_method_df$Ohat,breaks=1000)

Matrix decomposision method, sub-image

Now to do the same thing but in the presence of missing data. The SVD approach does not work for missing data so the missing data must be imputed before the SVD approach can be applied. Zhang et al. (2013) suggest the missing data be first replaced by the column or row mean, then estimate \(u\) and \(v\), replace missing data with \(u_iv_j\) and repeat until convergence, i.e., the estimates of \(u\) and \(v\) don’t change much. They say that starting the algorithm with the row or column mean makes no difference, but in our case the node screws everything us. Using the column means results in a band of dar columns in the middle and two lighter columns on the side. The row means come are very dark for the bottom half of the image and much lighter on the top. Therefore I impute the missing cells with the mean of the column and row means, which appears to work okay. The spline imputation method Maggie and Sarah have been using may provide better results but I haven’t tried yet.

subset <- m1_dat[,c("x","y","T2621")]
subset$T2621[sample(nrow(m1_dat),size=(.9*nrow(m1_dat)))] <- NA
ex_frame_samp <- matrix(subset$T2621,nrow=256,ncol=256,byrow = TRUE)
Bhat_missing <- lr_approx_missing(Y = ex_frame_samp,p = 1,lambda = 1)
Vo_method_df$Bhat_missing <- matrix(t(Bhat_missing$approx),ncol=1)
Vo_method_df$Ohat_missing <- Vo_method_df$Y - Vo_method_df$Bhat_missing
truth <- qplot(x,y,colour=Y,data=Vo_method_df)+theme_em()+ggtitle("Y (original)")
bground <- qplot(x,y,colour=Bhat_missing,data=Vo_method_df,size=I(.2))+theme_em()+ggtitle("B (background)")
leftover <- qplot(x,y,colour=Ohat_missing,data=Vo_method_df,size=I(.2))+theme_em()+ggtitle("F+E (leftover)")
grid.arrange(truth,bground,leftover,nrow=1)

Apply Maggie’s EM algorithm to the background corrected image. There results are for five groups. The red dots are groups 4 and 5 (which are considered growth) while the green dots are groups 1-3.

no_bg <- Vo_method_df$Ohat_missing
no_bg <- no_bg[-which(is.na(no_bg))]
#hist(no_bg,breaks=500)
mean_res_missing <- EM_alg_mu_cpp(z=no_bg,p = rep(1/5,5), mu = c(-50,-10,0,50,100), sigma = rep(4,5),eps = 1e-5,maxit = 1000)
Vo_method_df$Mean_class_missing <- Vo_method_df$Ohat_missing
Vo_method_df$Mean_class_missing[which(!is.na(Vo_method_df$Mean_class_missing ))] <-   apply(mean_res_missing$wmat,1,which.max)
non_missing_df <- subset(Vo_method_df,!is.na(Vo_method_df$Mean_class_missing))
non_missing_df1 <- subset(non_missing_df,Mean_class_missing>3)
non_missing_df2 <- subset(non_missing_df,Mean_class_missing<=3)
g_nong_missing <- ggplot(data=Vo_method_df)+geom_point(aes(x,y,colour=Y))+theme_em()+ggtitle("Estimated Growth") + geom_point(aes(x,y),colour=2,data=non_missing_df1)
g_nong_all <- ggplot(data=Vo_method_df)+geom_point(aes(x,y,colour=Y))+theme_em()+ggtitle("Estimated Growth") + geom_point(aes(x,y),colour=2,data=non_missing_df1)+
  geom_point(aes(x,y),colour='green',data=non_missing_df2)
grid.arrange(truth,g_nong_missing,g_nong_all,nrow=1)

Matrix Decomposition to Identify Growth Beginning

The singular values are a measure of how much of the signal in the image can be explained by the corresponding rank 1 approximation to the image. One would think that rank one matrices will do a better job of representing images without growth, i.e., only have a node and background, compare to images where there is a lot of growth going on. Test this by plotting the first singular value for the frames over time.

How about some of the later rank one matrices? Plot the singular values for the first five rank one approximations for five frames that exhibit no growth, initial stages of growth, max growth and dissipation.

try <- c("T199","T2162","T2287","T2621","T3666")
subset <- m1_dat[,c("x","y",try)]
s_mat <- matrix(0,length(try),5)
for(i in 3:ncol(subset)){
  subset[sample(nrow(m1_dat),size=(.9*nrow(m1_dat))),i] <- NA
  ex_frame_samp <- matrix(subset[,i],nrow=256,ncol=256,byrow = TRUE)
  Bhat_missing <- lr_approx_missing(Y = ex_frame_samp,p = 5,lambda = 1)
  s_mat[,(i-2)] <- Bhat_missing$ss
}
s_mat <- data.frame(s_mat)
s_mat_melt <- reshape2::melt(s_mat)
s_mat_melt$Index <- rep(1:5,5)

frame1 <- qplot(x,y,colour=T199,data=m1_dat)+theme_em()+ggtitle("X1")
frame2 <- qplot(x,y,colour=T2162,data=m1_dat)+theme_em()+ggtitle("X2")
frame3 <- qplot(x,y,colour=T2287,data=m1_dat)+theme_em()+ggtitle("X3")
frame4 <- qplot(x,y,colour=T2621,data=m1_dat)+theme_em()+ggtitle("X4")
frame5 <- qplot(x,y,colour=T3666,data=m1_dat)+theme_em()+ggtitle("X5")


full_pic <- qplot(Index,value,data=s_mat_melt,group=variable,colour=variable,geom='line')+geom_point()+theme(legend.position='none')+theme_bw()+
  ylab("Singular Value")+xlab("Dimension")
red_pic <- qplot(Index,value,data=s_mat_melt,group=variable,colour=variable,geom='line')+geom_point()+ylim(c(0,2000))+theme_bw()+xlim(2,5)+
  ylab("Singular Value")+xlab("Dimension")

lay <- rbind(c(1,2,3,4,5),
             c(6,6,7,7,7))

grid.arrange(frame1,frame2,frame3,frame4,frame5,full_pic,red_pic,layout_matrix=lay)
LS0tCnRpdGxlOiAiUlJTVkQgYmFja2dyb3VuZCBhZGp1c3RtZW50IgpvdXRwdXQ6IAogIGh0bWxfbm90ZWJvb2s6IAogICAgY29kZV9mb2xkaW5nOiBoaWRlCi0tLQoKYGBge3IsIGluY2x1ZGU9RkFMU0V9CmxpYnJhcnkoZ2dwbG90MikKbGlicmFyeShSb2JSU1ZEKQpsaWJyYXJ5KGdyaWRFeHRyYSkKUmNwcDo6c291cmNlQ3BwKCd+L0RvY3VtZW50cy9BSU0gUHJvamVjdCAoTGlzYSkvc3RyZWFtaW5nLXRjcy9FTV9Vc2VfQ2FzZS9Db2RlL09sZCBjb2RlL29sZF9FTV9mdW5jdGlvbnMuY3BwJykKc291cmNlKCd+L0RvY3VtZW50cy9BSU0gUHJvamVjdCAoTGlzYSkvc3RyZWFtaW5nLXRjcy9FTV9Vc2VfQ2FzZS9Db2RlL0dNTV9mdW5jdGlvbnNfQkFTLlInKQpzb3VyY2UoJ34vRG9jdW1lbnRzL0FJTSBQcm9qZWN0IChMaXNhKS9zdHJlYW1pbmctdGNzL0VNX1VzZV9DYXNlL0NvZGUvUGFya19NZXRob2QvbWF0cml4X2RlY29tcF9mdW5zLlInKQptMV9kYXQgPC0gcmVhZC5jc3YoIn4vRG9jdW1lbnRzL0FJTSBQcm9qZWN0IChMaXNhKS9FTV9Vc2VfQ2FzZS9Jbml0aWFsX21vdmllcy9NMV9kYXJrZGF0LmNzdiIpCm0xX2RhdCR5IDwtIDI1NS1tMV9kYXQkeQojVHVybiBmcmFtZSBpbnRvIDI1Ni1ieS0yNTYgbWF0cml4CmV4X2ZyYW1lIDwtIG1hdHJpeChtMV9kYXQkVDI2MjEgLG5yb3c9MjU2LG5jb2w9MjU2LGJ5cm93ID0gVFJVRSkKYGBgCgojTWF0cml4IERlY29tcG9zaXRpb24gTWV0aG9kLCBGdWxsIERhdGEKCltWbyBhbmQgUGFyayAoMjAxNildKGh0dHBzOi8vYXJ4aXYub3JnL2Ficy8xNjA5LjA4MDc4KSB1c2VkIGEgbWF0cml4IGRlY29tcG9zaXRpb24gYXBwcm9hY2ggdG8gZXN0aW1hdGUgYmFja2dyb3VuZCwgZm9yZWdyb3VuZCBhbmQgbm9pc2UgaW4gRU0gaW1hZ2VzLiAgVGhlIG1hdGggYmVoaW5kIHRoZWlyIG1ldGhvZCB3YXMgd29ya2VkIG91dCBieSBbWmhhbmcgZXQgYWwuICgyMDEzKV0oaHR0cHM6Ly9hcnhpdi5vcmcvYWJzLzEzMTEuNzQ4MCkgIFRoYXQgaXMsIGlmICRZJCBpcyBhICRtXHRpbWVzIG4kIG1hdHJpeCB3aGVyZSAkeV97aWp9JCBpcyB0aGUgaW50ZW5zaXR5IHZhbHVlIGF0IHRoZSAkeCQgYW5kICR5JCBsb2NhdGlvbnMuICBUaGVuICRZJCBjYW4gYmUgZGVjb21wb3NlZCBpbnRvICRCJCwgJEYkIGFuZCAkRSQgY29ycmVzcG9uZGluZyB0byBiYWNrZ3JvdW5kLCBmb3JlZ3JvdW5kIGFuZCBlcnJvciwgcmVzcGVjdGl2ZWx5LCB0aHJvdWdoCiQkWSA9IEIgKyBGICsgRS4kJAoKJEIkIGlzIGVzdGltYXRlZCBmaXJzdCB1c2luZyBhIHJlZ3VsYXJpemVkIGxvdy1yYW5rIGFwcHJveGltYXRpb24gJCRcaGF0IEJfXGxhbWJkYT1cc3VtX3trPTF9XnBcaGF0e1xtYXRoYmZ7dX19X1xsYW1iZGFcaGF0e1xtYXRoYmZ7dn19X1xsYW1iZGFeXHRvcCQkIHdoZXJlICRcaGF0e1xtYXRoYmZ7dX19X1xsYW1iZGEkIGlzIHRoZSAkbVx0aW1lcyAxJCB1bm5vcm1hbGl6ZWQgbGVmdCBzaW5ndWxhciB2ZWN0b3IgZXN0aW1hdGVkIHVzaW5nIHJlZ3VsYXJpemVkLCByb2J1c3QgU1ZEIHdpdGggcGVuYWx0eSBwYXJhbWV0ZXIgJFxsYW1iZGEkIGFuZCAkXGhhdHtcbWF0aGJme3Z9fV9cbGFtYmRhJCBpcyB0aGUgJG5cdGltZXMgMSQgcmlnaHQgc2luZ3VsYXIgdmVjdG9yIHdpdGggdW5pdCBub3JtIGVzdGltYXRlZCB1c2luZyBSUlNWRCB3aXRoIHBlbmFsdHkgJFxsYW1iZGEkLiAgVGhlIHJhbmsgb2YgdGhlIGFwcHJveGltYXRpb24gYW5kIHRoZSBwZW5hbHR5IHBhcmFtZXRlciAkXGxhbWJkYSQgbmVlZHMgdG8gYmUgY2hvc2VuIG9uIGEgY2FzZSBieSBjYXNlIGJhc2lzLiAgQSBmZXcgZXhhbXBsZSBlc3RpbWF0ZXMgb2YgJEIkIHdpdGggZGlmZmVyZW50ICRcbGFtYmRhJCB2YWx1ZXMgaXMgYmVsb3cuICBFYWNoIG9mIHRoZSBlc3RpbWF0ZXMgaXMgYW4gJDhee3RofSQgZGVncmVlIGFwcHJveGltYXRpb24uICBTaW1pbGFyIHRvIHJlZ3VsYXJpemVkIHJlZ3Jlc3Npb24sIGxhcmdlIHZhbHVlcyBvZiAkXGxhbWJkYSQgc21vb3RoIG91dCB0aGUgYmFja2dyb3VuZCBlc3RpbWF0ZSB3aGlsZSBzbWFsbCB2YWx1ZXMgcmVzdWx0IGluIGEgdmVyeSBzLgoKYGBge3IsIGV2YWw9RkFMU0V9CiNDcmVhdGUgJ0JoYXRfbGlzdCcgb2JqZWN0LCB0YWtlcyBhIHdoaWxlIHNvIG9ubHkgcnVuIG9uY2UgYW5kIGxvYWQgdGhlIHJlc3VsdCBpbiB0aGUgbmV4dCBjaHVuY2sKI1JvYnVzdCBTVkQgb2YgZXhfZnJhbWUgaW4gb3JkZXIgdG8gZXN0aW1hdGUgYmFja2dyb3VuZCBtYXRyaXggKHNlY3Rpb24gMi4xKSwgcmFuayBwCnAgPC0gMQpsYW1zIDwtIGMoMCwxLDEwLDIwLDUwKQpCaGF0X2xpc3QgPC0gdmVjdG9yKCJsaXN0IixsZW5ndGgobGFtcykpCnNfcyA8LSBtYXRyaXgoMCxsZW5ndGgobGFtcykscCkKZm9yKGogaW4gMTpsZW5ndGgobGFtcykpewogIEJoYXQgPC0gbWF0cml4KDAsMjU2LDI1NikKICB5IDwtIGV4X2ZyYW1lCiAgZm9yKGkgaW4gMTpwKXsKICAgIHkgPC0gZXhfZnJhbWUgLSBCaGF0CiAgICByc3ZkaSA8LSAgUm9iUlNWRCh5LCBpcm9idXN0PVRSVUUsIG5pdGVyPTEwMCx1c3BhciA9IGxhbXNbal0sIHZzcGFyID0gbGFtc1tqXSkKICAgIEJoYXQgPC0gQmhhdCArIHJzdmRpJHUlKiV0KHJzdmRpJHYpKnJzdmRpJHMKICAgIHNfc1tqLGldIDwtIHJzdmRpJHMKICB9CiAgQmhhdF9saXN0W1tqXV0gPC0gQmhhdAp9CiNwbG90KHNfc1syLC1jKDE6MildKQojc2F2ZShCaGF0X2xpc3QsZmlsZT0iL1VzZXJzL3N0YW4wNzAvRG9jdW1lbnRzL0FJTSBQcm9qZWN0IChMaXNhKS9zdHJlYW1pbmctdGNzL0VNX1VzZV9DYXNlL1dyaXRlX1Vwcy9CaGF0LlJkYXRhIikKYGBgCgpgYGB7cixmaWcud2lkdGg9MTUsZmlnLmhlaWdodD0zfQpsb2FkKCJ+L0RvY3VtZW50cy9BSU0gUHJvamVjdCAoTGlzYSkvc3RyZWFtaW5nLXRjcy9FTV9Vc2VfQ2FzZS9Xcml0ZV9VcHMvQmhhdC5SZGF0YSIpClZvX21ldGhvZF9kZiA8LSBkYXRhLmZyYW1lKHg9bTFfZGF0JHgseT1tMV9kYXQkeSwgWSA9IG1hdHJpeCh0KGV4X2ZyYW1lKSxuY29sPTEpKQpWb19tZXRob2RfZGYkQmhhdCA8LSBtYXRyaXgodChCaGF0X2xpc3RbWzFdXSksbmNvbD0xKQpwbG90MSA8LSBxcGxvdCh4LHksY29sb3VyPUJoYXQsZGF0YT1Wb19tZXRob2RfZGYpK3RoZW1lX2VtKCkrZ2d0aXRsZShleHByZXNzaW9uKGxhbWJkYT09MCkpClZvX21ldGhvZF9kZiRCaGF0IDwtIG1hdHJpeCh0KEJoYXRfbGlzdFtbMl1dKSxuY29sPTEpCnBsb3QyIDwtIHFwbG90KHgseSxjb2xvdXI9QmhhdCxkYXRhPVZvX21ldGhvZF9kZikrdGhlbWVfZW0oKStnZ3RpdGxlKGV4cHJlc3Npb24obGFtYmRhPT0xKSkKVm9fbWV0aG9kX2RmJEJoYXQgPC0gbWF0cml4KHQoQmhhdF9saXN0W1szXV0pLG5jb2w9MSkKcGxvdDMgPC0gcXBsb3QoeCx5LGNvbG91cj1CaGF0LGRhdGE9Vm9fbWV0aG9kX2RmKSt0aGVtZV9lbSgpK2dndGl0bGUoZXhwcmVzc2lvbihsYW1iZGE9PTEwKSkKVm9fbWV0aG9kX2RmJEJoYXQgPC0gbWF0cml4KHQoQmhhdF9saXN0W1s0XV0pLG5jb2w9MSkKcGxvdDQgPC0gcXBsb3QoeCx5LGNvbG91cj1CaGF0LGRhdGE9Vm9fbWV0aG9kX2RmKSt0aGVtZV9lbSgpK2dndGl0bGUoZXhwcmVzc2lvbihsYW1iZGE9PTIwKSkKVm9fbWV0aG9kX2RmJEJoYXQgPC0gbWF0cml4KHQoQmhhdF9saXN0W1s1XV0pLG5jb2w9MSkKcGxvdDUgPC0gcXBsb3QoeCx5LGNvbG91cj1CaGF0LGRhdGE9Vm9fbWV0aG9kX2RmKSt0aGVtZV9lbSgpK2dndGl0bGUoZXhwcmVzc2lvbihsYW1iZGE9PTUwKSkKZ3JpZC5hcnJhbmdlKHBsb3QxLHBsb3QyLHBsb3QzLHBsb3Q0LHBsb3Q1LG5yb3c9MSkKVm9fbWV0aG9kX2RmJEJoYXQgPC0gbWF0cml4KHQoQmhhdF9saXN0W1syXV0pLG5jb2w9MSkKcm0oQmhhdF9saXN0KQpgYGAKClRoZSBkZWNvbXBvc2l0aW9uIG9mIHRoZSBvcmlnaW5hbCBkYXRhICgkWSQsIGxlZnQgcGxvdCkgaW50byBiYWNrZ3JvdW5kICgkQiQsIG1pZGRsZSBwbG90KSBhbmQgbGVmdG92ZXIgKCRGK0UkLCByaWdodCBwbG90KSB1c2luZyAkXGxhbWJkYT0xJCBpcyBiZWxvdy4gIFRoZSByaWdodCBwbG90IGRvZXMgc2VlbSB0byBoYXZlIHRoZSBsZWZ0LXRvLXJpZ2h0IGdyYWRpZW50IHJlbW92ZWQsIGJ1dCBpdCBsaWdodGVucyB0aGUgbm9kZSB1cCBhIGJpdCB0b28gbXVjaC4KCmBgYHtyLCBmaWcud2lkdGg9MTUsZmlnLmhlaWdodD01fQpWb19tZXRob2RfZGYkT2hhdCA8LSBWb19tZXRob2RfZGYkWSAtIFZvX21ldGhvZF9kZiRCaGF0Cgp0cnV0aCA8LSBxcGxvdCh4LHksY29sb3VyPVksZGF0YT1Wb19tZXRob2RfZGYpK3RoZW1lX2VtKCkrZ2d0aXRsZSgiWSAob3JpZ2luYWwpIikKYmdyb3VuZCA8LSBxcGxvdCh4LHksY29sb3VyPUJoYXQsZGF0YT1Wb19tZXRob2RfZGYpK3RoZW1lX2VtKCkrZ2d0aXRsZSgiQiAoYmFja2dyb3VuZCkiKQpsZWZ0b3ZlciA8LSBxcGxvdCh4LHksY29sb3VyPU9oYXQsZGF0YT1Wb19tZXRob2RfZGYpK3RoZW1lX2VtKCkrZ2d0aXRsZSgiRitFIChsZWZ0b3ZlcikiKQpncmlkLmFycmFuZ2UodHJ1dGgsYmdyb3VuZCxsZWZ0b3Zlcixucm93PTEpCmBgYAoKYGBge3IsZmlnLndpZHRoPTEwLGZpZy5oZWlnaHQ9MTB9CnAgPC0gMTYKbGFtYmRhIDwtIDEKaW1ncyA8LSB2ZWN0b3IoImxpc3QiLHApCmFsbF9wbG90cyA8LSB2ZWN0b3IoImxpc3QiLHApCmFwcHJveCA8LSBtYXRyaXgoMCwyNTYsMjU2KQpzX3MgPC0gcmVwKE5BLHApCmZvcihpIGluIDE6cCl7CiAgeSA8LSBleF9mcmFtZSAtIGFwcHJveAogIHJzdmRpIDwtICBSb2JSU1ZEKHksIGlyb2J1c3Q9VFJVRSwgbml0ZXI9NTAwLHVzcGFyID0gbGFtYmRhLCB2c3BhciA9IGxhbWJkYSkKICBpbWdzW1tpXV0gPC0gIHJzdmRpJHUlKiV0KHJzdmRpJHYpKnJzdmRpJHMKICBhcHByb3ggPC0gYXBwcm94ICsgaW1nc1tbaV1dCiAgc19zW2ldIDwtIHJzdmRpJHMKICBvbmVfZF9kZiA8LSBkYXRhLmZyYW1lKHg9bTFfZGF0JHgseT1tMV9kYXQkeSwgSW50PW1hdHJpeCh0KGltZ3NbW2ldXSksbmNvbD0xKSkKICBhbGxfcGxvdHNbW2ldXSA8LSBxcGxvdCh4LHksY29sb3VyPUludCxkYXRhPW9uZV9kX2RmKSt0aGVtZV9lbSgpK2dndGl0bGUocGFzdGUoIkRpbWVuc2lvbiIsaSkpCn0KI3Bsb3Qoc19zKQpncmlkLmFycmFuZ2UoZ3JvYnM9YWxsX3Bsb3RzLG5yb3c9NCxuY29sPTQpCiNzdW0oc19zKS8oMjU2XjIpCmBgYAoKVGhleSB0aGVuIHVzZSB0aGUgcm9idXN0LCByZWd1bGFyaXplZCBTVkQgYXBwcm9hY2ggYWdhaW4gdG8gZGVjb21wb3NlIHdoYXQncyBsZWZ0IG92ZXIgKCRPJCkgaW50byBmb3JlZ3JvdW5kIGFuZCByZXNpZHVhbCwgYnV0IEkgaGF2ZW4ndCBnb3R0ZW4gdGhhdCB0byBnaXZlIGNvbnNpc3RlbnQgcmVzdWx0cy4gIEluc3RlYWQsIEkgYXBwbHkgTWFnZ2llJ3MgRU0gYXBwcm9hY2ggd2l0aCBubyBiYWNrZ3JvdW5kIHRvIGNsdXN0ZXIgdGhlICJsZWZ0LW92ZXIiIHBpeGVscyBpbnRvIGdyb3d0aCBhbmQgbm9uLWdyb3d0aC4KCmBgYHtyLGZpZy53aWR0aD0xMCxmaWcuaGVpZ2h0PTV9CiNBcHBseSBFTSB3aXRob3V0IGJhY2tncm91bmQgYWRqdXN0bWVudAptZWFuX3JlcyA8LSBFTV9hbGdfbXVfY3BwKHo9Vm9fbWV0aG9kX2RmJE9oYXQscCA9IHJlcCgxLzUsNSksIG11ID0gYygtNTAsMCwyNSw1MCwxMDApLCBzaWdtYSA9IHJlcCg0LDUpLGVwcyA9IDFlLTUsbWF4aXQgPSAxMDAwKQpWb19tZXRob2RfZGYkTWVhbl9jbGFzcyA8LSBhcy5mYWN0b3IoYXBwbHkobWVhbl9yZXMkd21hdCwxLHdoaWNoLm1heCkpCmdfbm9uZyA8LSBxcGxvdCh4LHksY29sb3VyPU1lYW5fY2xhc3MsZGF0YT1Wb19tZXRob2RfZGYsc2l6ZT1JKC4xKSkrdGhlbWVfZW0oKStzY2FsZV9jb2xvdXJfbWFudWFsKHZhbHVlcz1jKDEsMSwyLDIsMikpK2dndGl0bGUoIkdyb3d0aCIpCmdyaWQuYXJyYW5nZSh0cnV0aCxnX25vbmcsbnJvdz0xKQojaGlzdChWb19tZXRob2RfZGYkT2hhdCxicmVha3M9MTAwMCkKYGBgCgojTWF0cml4IGRlY29tcG9zaXNpb24gbWV0aG9kLCBzdWItaW1hZ2UKCk5vdyB0byBkbyB0aGUgc2FtZSB0aGluZyBidXQgaW4gdGhlIHByZXNlbmNlIG9mIG1pc3NpbmcgZGF0YS4gIFRoZSBTVkQgYXBwcm9hY2ggZG9lcyBub3Qgd29yayBmb3IgbWlzc2luZyBkYXRhIHNvIHRoZSBtaXNzaW5nIGRhdGEgbXVzdCBiZSBpbXB1dGVkIGJlZm9yZSB0aGUgU1ZEIGFwcHJvYWNoIGNhbiBiZSBhcHBsaWVkLiAgW1poYW5nIGV0IGFsLiAoMjAxMyldKGh0dHBzOi8vYXJ4aXYub3JnL2Ficy8xMzExLjc0ODApIHN1Z2dlc3QgdGhlIG1pc3NpbmcgZGF0YSBiZSBmaXJzdCByZXBsYWNlZCBieSB0aGUgY29sdW1uIG9yIHJvdyBtZWFuLCB0aGVuIGVzdGltYXRlICR1JCBhbmQgJHYkLCByZXBsYWNlIG1pc3NpbmcgZGF0YSB3aXRoICR1X2l2X2okIGFuZCByZXBlYXQgdW50aWwgY29udmVyZ2VuY2UsIGkuZS4sIHRoZSBlc3RpbWF0ZXMgb2YgJHUkIGFuZCAkdiQgZG9uJ3QgY2hhbmdlIG11Y2guICBUaGV5IHNheSB0aGF0IHN0YXJ0aW5nIHRoZSBhbGdvcml0aG0gd2l0aCB0aGUgcm93IG9yIGNvbHVtbiBtZWFuIG1ha2VzIG5vIGRpZmZlcmVuY2UsIGJ1dCBpbiBvdXIgY2FzZSB0aGUgbm9kZSBzY3Jld3MgZXZlcnl0aGluZyB1cy4gIFVzaW5nIHRoZSBjb2x1bW4gbWVhbnMgcmVzdWx0cyBpbiBhIGJhbmQgb2YgZGFyIGNvbHVtbnMgaW4gdGhlIG1pZGRsZSBhbmQgdHdvIGxpZ2h0ZXIgY29sdW1ucyBvbiB0aGUgc2lkZS4gIFRoZSByb3cgbWVhbnMgY29tZSBhcmUgdmVyeSBkYXJrIGZvciB0aGUgYm90dG9tIGhhbGYgb2YgdGhlIGltYWdlIGFuZCBtdWNoIGxpZ2h0ZXIgb24gdGhlIHRvcC4gIFRoZXJlZm9yZSBJIGltcHV0ZSB0aGUgbWlzc2luZyBjZWxscyB3aXRoIHRoZSBtZWFuIG9mIHRoZSBjb2x1bW4gYW5kIHJvdyBtZWFucywgd2hpY2ggYXBwZWFycyB0byB3b3JrIG9rYXkuICBUaGUgc3BsaW5lIGltcHV0YXRpb24gbWV0aG9kIE1hZ2dpZSBhbmQgU2FyYWggaGF2ZSBiZWVuIHVzaW5nIG1heSBwcm92aWRlIGJldHRlciByZXN1bHRzIGJ1dCBJIGhhdmVuJ3QgdHJpZWQgeWV0LgoKCmBgYHtyLCBmaWcud2lkdGg9MTUsZmlnLmhlaWdodD01fQpzdWJzZXQgPC0gbTFfZGF0WyxjKCJ4IiwieSIsIlQyNjIxIildCnN1YnNldCRUMjYyMVtzYW1wbGUobnJvdyhtMV9kYXQpLHNpemU9KC45Km5yb3cobTFfZGF0KSkpXSA8LSBOQQpleF9mcmFtZV9zYW1wIDwtIG1hdHJpeChzdWJzZXQkVDI2MjEsbnJvdz0yNTYsbmNvbD0yNTYsYnlyb3cgPSBUUlVFKQoKQmhhdF9taXNzaW5nIDwtIGxyX2FwcHJveF9taXNzaW5nKFkgPSBleF9mcmFtZV9zYW1wLHAgPSAxLGxhbWJkYSA9IDEpClZvX21ldGhvZF9kZiRCaGF0X21pc3NpbmcgPC0gbWF0cml4KHQoQmhhdF9taXNzaW5nJGFwcHJveCksbmNvbD0xKQpWb19tZXRob2RfZGYkT2hhdF9taXNzaW5nIDwtIFZvX21ldGhvZF9kZiRZIC0gVm9fbWV0aG9kX2RmJEJoYXRfbWlzc2luZwp0cnV0aCA8LSBxcGxvdCh4LHksY29sb3VyPVksZGF0YT1Wb19tZXRob2RfZGYpK3RoZW1lX2VtKCkrZ2d0aXRsZSgiWSAob3JpZ2luYWwpIikKYmdyb3VuZCA8LSBxcGxvdCh4LHksY29sb3VyPUJoYXRfbWlzc2luZyxkYXRhPVZvX21ldGhvZF9kZixzaXplPUkoLjIpKSt0aGVtZV9lbSgpK2dndGl0bGUoIkIgKGJhY2tncm91bmQpIikKbGVmdG92ZXIgPC0gcXBsb3QoeCx5LGNvbG91cj1PaGF0X21pc3NpbmcsZGF0YT1Wb19tZXRob2RfZGYsc2l6ZT1JKC4yKSkrdGhlbWVfZW0oKStnZ3RpdGxlKCJGK0UgKGxlZnRvdmVyKSIpCmdyaWQuYXJyYW5nZSh0cnV0aCxiZ3JvdW5kLGxlZnRvdmVyLG5yb3c9MSkKYGBgCgpBcHBseSBNYWdnaWUncyBFTSBhbGdvcml0aG0gdG8gdGhlIGJhY2tncm91bmQgY29ycmVjdGVkIGltYWdlLiAgVGhlcmUgcmVzdWx0cyBhcmUgZm9yIGZpdmUgZ3JvdXBzLiAgVGhlIHJlZCBkb3RzIGFyZSBncm91cHMgNCBhbmQgNSAod2hpY2ggYXJlIGNvbnNpZGVyZWQgZ3Jvd3RoKSB3aGlsZSB0aGUgZ3JlZW4gZG90cyBhcmUgZ3JvdXBzIDEtMy4KCmBgYHtyLGZpZy53aWR0aD0xNSxmaWcuaGVpZ2h0PTV9Cm5vX2JnIDwtIFZvX21ldGhvZF9kZiRPaGF0X21pc3NpbmcKbm9fYmcgPC0gbm9fYmdbLXdoaWNoKGlzLm5hKG5vX2JnKSldCiNoaXN0KG5vX2JnLGJyZWFrcz01MDApCm1lYW5fcmVzX21pc3NpbmcgPC0gRU1fYWxnX211X2NwcCh6PW5vX2JnLHAgPSByZXAoMS81LDUpLCBtdSA9IGMoLTUwLC0xMCwwLDUwLDEwMCksIHNpZ21hID0gcmVwKDQsNSksZXBzID0gMWUtNSxtYXhpdCA9IDEwMDApClZvX21ldGhvZF9kZiRNZWFuX2NsYXNzX21pc3NpbmcgPC0gVm9fbWV0aG9kX2RmJE9oYXRfbWlzc2luZwpWb19tZXRob2RfZGYkTWVhbl9jbGFzc19taXNzaW5nW3doaWNoKCFpcy5uYShWb19tZXRob2RfZGYkTWVhbl9jbGFzc19taXNzaW5nICkpXSA8LSAgIGFwcGx5KG1lYW5fcmVzX21pc3Npbmckd21hdCwxLHdoaWNoLm1heCkKCgpub25fbWlzc2luZ19kZiA8LSBzdWJzZXQoVm9fbWV0aG9kX2RmLCFpcy5uYShWb19tZXRob2RfZGYkTWVhbl9jbGFzc19taXNzaW5nKSkKbm9uX21pc3NpbmdfZGYxIDwtIHN1YnNldChub25fbWlzc2luZ19kZixNZWFuX2NsYXNzX21pc3Npbmc+MykKbm9uX21pc3NpbmdfZGYyIDwtIHN1YnNldChub25fbWlzc2luZ19kZixNZWFuX2NsYXNzX21pc3Npbmc8PTMpCgpnX25vbmdfbWlzc2luZyA8LSBnZ3Bsb3QoZGF0YT1Wb19tZXRob2RfZGYpK2dlb21fcG9pbnQoYWVzKHgseSxjb2xvdXI9WSkpK3RoZW1lX2VtKCkrZ2d0aXRsZSgiRXN0aW1hdGVkIEdyb3d0aCIpICsgZ2VvbV9wb2ludChhZXMoeCx5KSxjb2xvdXI9MixkYXRhPW5vbl9taXNzaW5nX2RmMSkKCmdfbm9uZ19hbGwgPC0gZ2dwbG90KGRhdGE9Vm9fbWV0aG9kX2RmKStnZW9tX3BvaW50KGFlcyh4LHksY29sb3VyPVkpKSt0aGVtZV9lbSgpK2dndGl0bGUoIkVzdGltYXRlZCBHcm93dGgiKSArIGdlb21fcG9pbnQoYWVzKHgseSksY29sb3VyPTIsZGF0YT1ub25fbWlzc2luZ19kZjEpKwogIGdlb21fcG9pbnQoYWVzKHgseSksY29sb3VyPSdncmVlbicsZGF0YT1ub25fbWlzc2luZ19kZjIpCgpncmlkLmFycmFuZ2UodHJ1dGgsZ19ub25nX21pc3NpbmcsZ19ub25nX2FsbCxucm93PTEpCmBgYAoKI01hdHJpeCBEZWNvbXBvc2l0aW9uIHRvIElkZW50aWZ5IEdyb3d0aCBCZWdpbm5pbmcKCgpUaGUgc2luZ3VsYXIgdmFsdWVzIGFyZSBhIG1lYXN1cmUgb2YgaG93IG11Y2ggb2YgdGhlIHNpZ25hbCBpbiB0aGUgaW1hZ2UgY2FuIGJlIGV4cGxhaW5lZCBieSB0aGUgY29ycmVzcG9uZGluZyByYW5rIDEgYXBwcm94aW1hdGlvbiB0byB0aGUgaW1hZ2UuICBPbmUgd291bGQgdGhpbmsgdGhhdCByYW5rIG9uZSBtYXRyaWNlcyB3aWxsIGRvIGEgYmV0dGVyIGpvYiBvZiByZXByZXNlbnRpbmcgaW1hZ2VzIHdpdGhvdXQgZ3Jvd3RoLCBpLmUuLCBvbmx5IGhhdmUgYSBub2RlIGFuZCBiYWNrZ3JvdW5kLCBjb21wYXJlIHRvIGltYWdlcyB3aGVyZSB0aGVyZSBpcyBhIGxvdCBvZiBncm93dGggZ29pbmcgb24uICBUZXN0IHRoaXMgYnkgcGxvdHRpbmcgdGhlIGZpcnN0IHNpbmd1bGFyIHZhbHVlIGZvciB0aGUgZnJhbWVzIG92ZXIgdGltZS4KCgpgYGB7cn0Kc2luZ3VsYXJfZGYgPC0gZGF0YS5mcmFtZShGcmFtZT1jb2xuYW1lcyhtMV9kYXQpWy1jKDE6MildLFZhbHVlPU5BKQpmb3IoaSBpbiAxOm5yb3coc2luZ3VsYXJfZGYpKXsKICBzdWJzZXQgPC0gbTFfZGF0WyxjKDEsMiwoaSsyKSldCiAgc3Vic2V0W3NhbXBsZShucm93KG0xX2RhdCksc2l6ZT0oLjkqbnJvdyhtMV9kYXQpKSksM10gPC0gTkEKICBleF9mcmFtZV9zYW1wIDwtIG1hdHJpeChzdWJzZXRbLDNdLG5yb3c9MjU2LG5jb2w9MjU2LGJ5cm93ID0gVFJVRSkKICBCaGF0X21pc3NpbmcgPC0gbHJfYXBwcm94X21pc3NpbmcoWSA9IGV4X2ZyYW1lX3NhbXAscCA9IDEsbGFtYmRhID0gMSkKICBzaW5ndWxhcl9kZiRWYWx1ZVtpXSA8LSBCaGF0X21pc3Npbmckc3MKfQpzaW5ndWxhcl9kZiRGcmFtZU51bSA8LSAxOm5yb3coc2luZ3VsYXJfZGYpCnFwbG90KEZyYW1lTnVtLFZhbHVlLGRhdGE9c2luZ3VsYXJfZGYpCmBgYAoKCkhvdyBhYm91dCBzb21lIG9mIHRoZSBsYXRlciByYW5rIG9uZSBtYXRyaWNlcz8gIFBsb3QgdGhlIHNpbmd1bGFyIHZhbHVlcyBmb3IgdGhlIGZpcnN0IGZpdmUgcmFuayBvbmUgYXBwcm94aW1hdGlvbnMgZm9yIGZpdmUgZnJhbWVzIHRoYXQgZXhoaWJpdCBubyBncm93dGgsIGluaXRpYWwgc3RhZ2VzIG9mIGdyb3d0aCwgbWF4IGdyb3d0aCBhbmQgZGlzc2lwYXRpb24uCgoKYGBge3IsZmlnLndpZHRoPTE1LGhlaWdodD02LGRwaT0yMDB9CnRyeSA8LSBjKCJUMTk5IiwiVDIxNjIiLCJUMjI4NyIsIlQyNjIxIiwiVDM2NjYiKQpzdWJzZXQgPC0gbTFfZGF0WyxjKCJ4IiwieSIsdHJ5KV0Kc19tYXQgPC0gbWF0cml4KDAsbGVuZ3RoKHRyeSksNSkKZm9yKGkgaW4gMzpuY29sKHN1YnNldCkpewogIHN1YnNldFtzYW1wbGUobnJvdyhtMV9kYXQpLHNpemU9KC45Km5yb3cobTFfZGF0KSkpLGldIDwtIE5BCiAgZXhfZnJhbWVfc2FtcCA8LSBtYXRyaXgoc3Vic2V0WyxpXSxucm93PTI1NixuY29sPTI1NixieXJvdyA9IFRSVUUpCiAgQmhhdF9taXNzaW5nIDwtIGxyX2FwcHJveF9taXNzaW5nKFkgPSBleF9mcmFtZV9zYW1wLHAgPSA1LGxhbWJkYSA9IDEpCiAgc19tYXRbLChpLTIpXSA8LSBCaGF0X21pc3Npbmckc3MKfQpzX21hdCA8LSBkYXRhLmZyYW1lKHNfbWF0KQpzX21hdF9tZWx0IDwtIHJlc2hhcGUyOjptZWx0KHNfbWF0KQpzX21hdF9tZWx0JEluZGV4IDwtIHJlcCgxOjUsNSkKCmZyYW1lMSA8LSBxcGxvdCh4LHksY29sb3VyPVQxOTksZGF0YT1tMV9kYXQpK3RoZW1lX2VtKCkrZ2d0aXRsZSgiWDEiKQpmcmFtZTIgPC0gcXBsb3QoeCx5LGNvbG91cj1UMjE2MixkYXRhPW0xX2RhdCkrdGhlbWVfZW0oKStnZ3RpdGxlKCJYMiIpCmZyYW1lMyA8LSBxcGxvdCh4LHksY29sb3VyPVQyMjg3LGRhdGE9bTFfZGF0KSt0aGVtZV9lbSgpK2dndGl0bGUoIlgzIikKZnJhbWU0IDwtIHFwbG90KHgseSxjb2xvdXI9VDI2MjEsZGF0YT1tMV9kYXQpK3RoZW1lX2VtKCkrZ2d0aXRsZSgiWDQiKQpmcmFtZTUgPC0gcXBsb3QoeCx5LGNvbG91cj1UMzY2NixkYXRhPW0xX2RhdCkrdGhlbWVfZW0oKStnZ3RpdGxlKCJYNSIpCgoKZnVsbF9waWMgPC0gcXBsb3QoSW5kZXgsdmFsdWUsZGF0YT1zX21hdF9tZWx0LGdyb3VwPXZhcmlhYmxlLGNvbG91cj12YXJpYWJsZSxnZW9tPSdsaW5lJykrZ2VvbV9wb2ludCgpK3RoZW1lKGxlZ2VuZC5wb3NpdGlvbj0nbm9uZScpK3RoZW1lX2J3KCkrCiAgeWxhYigiU2luZ3VsYXIgVmFsdWUiKSt4bGFiKCJEaW1lbnNpb24iKQpyZWRfcGljIDwtIHFwbG90KEluZGV4LHZhbHVlLGRhdGE9c19tYXRfbWVsdCxncm91cD12YXJpYWJsZSxjb2xvdXI9dmFyaWFibGUsZ2VvbT0nbGluZScpK2dlb21fcG9pbnQoKSt5bGltKGMoMCwyMDAwKSkrdGhlbWVfYncoKSt4bGltKDIsNSkrCiAgeWxhYigiU2luZ3VsYXIgVmFsdWUiKSt4bGFiKCJEaW1lbnNpb24iKQoKbGF5IDwtIHJiaW5kKGMoMSwyLDMsNCw1KSwKICAgICAgICAgICAgIGMoNiw2LDcsNyw3KSkKCmdyaWQuYXJyYW5nZShmcmFtZTEsZnJhbWUyLGZyYW1lMyxmcmFtZTQsZnJhbWU1LGZ1bGxfcGljLHJlZF9waWMsbGF5b3V0X21hdHJpeD1sYXkpCmBgYAoKCgoKCgoKCgoK